%%%-------------------------------------------------------------------
%%% File    : p36.erl
%%% Author  : Plamen Dragozov <plamen at dragozov.com>
%%% Description : 
%%% The decimal number, 585 = 1001001001_(2) (binary), is palindromic 
%%% in both bases.
%%%
%%% Find the sum of all numbers, less than one million, which are 
%%% palindromic in base 10 and base 2.
%%%
%%% (Please note that the palindromic number, in either base, may not 
%%% include leading zeros.)
%%%
%%%
%%% Created : 29 Dec 2008
%%%-------------------------------------------------------------------
-module(p36).
%% API
-compile(export_all).

solution(Limit) ->
    Size = pow10(Limit - 1) + 1,
    All = palindrome_iterator(fun(X, Acc)-> 
                                      case X < Limit andalso is_palindrome_base2(X) of
                                          true ->
                                              [X|Acc];
                                          _ -> Acc
                                      end
                              end, 
                              Size),
    {lists:sum(All) + 1, [1|All]}.

% A palindrome of N digits can be represented by a number of N/2 digits glued with its reversed copy if N is even or
% with its reversed copy without the first digit if N is odd.
% Example:
% 987789 = 987*1000 + 789
% 98789 = 987*100 + (789 rem 100)
%Returns a palindrome, created from a number half its length as described above
palindrome(Half, Pow10, even) ->
    Half*Pow10*10 + reverse(Half, Pow10);
palindrome(Half, Pow10, odd) ->
    Half*Pow10 + (reverse(Half, Pow10) rem Pow10).

%Iterates through all palindromes of a given size (number of digits) or less, applies the Fun function to each and returns the first result different than false (or null if no more left).
palindrome_iterator(Fun, Size) ->
    Half = (Size + 1) div 2,
    Pow10 = trunc(math:pow(10, Half - 1)),
    IsEven = case (Size rem 2) =:= 0 of
                 true -> even;
                 _ -> odd
             end,
%    io:format("~p,~p,~p,~p~n", [Size, Half, Pow10, IsEven]),
    palindrome_iterator(Fun, Pow10*10 - 1, Pow10, IsEven, []).

palindrome_iterator(_, 0, _, _, Acc) -> 
%    io:format("0:At 0!~n"),
    Acc;

palindrome_iterator(Fun, Next, Pow10, even, Acc) when Pow10 =:= Next ->
%    io:format("1:~p,~p,~p~n", [Next, Pow10, even]),    
    palindrome_iterator(Fun, Pow10*10 - 1 , Pow10, odd, Acc);
palindrome_iterator(Fun, Next, Pow10, odd, Acc) when Pow10 =:= Next ->
%   io:format("2:~p,~p,~p~n", [Next, Pow10, odd]),    
    palindrome_iterator(Fun, Pow10 - 1 , Pow10 div 10, even, Acc);
palindrome_iterator(Fun, Next, Pow10, IsEven, Acc) ->
%    io:format("3:~p,~p,~p~n", [Next, Pow10, IsEven]),    
    P = palindrome(Next, Pow10, IsEven),
    palindrome_iterator(Fun, Next - 1, Pow10, IsEven, Fun(P, Acc)).

is_palindrome_base2(N) ->
    DigitsB2 = to_base2(N),
    Size = array:size(DigitsB2),
    is_palindrome_base2(0, DigitsB2, Size, Size div 2).
is_palindrome_base2(I, DigitsB2, Size, Half) when I < Half->
    case array:get(I, DigitsB2) =:= array:get(Size - 1 - I, DigitsB2) of
        true ->
            is_palindrome_base2(I+1, DigitsB2, Size, Half);
        _ -> false
    end;
is_palindrome_base2(_, _, _, _) -> true.

%Convert an integer to an array of the digits of its base 2 representation.
to_base2(N) ->
    to_base2(N, []).

to_base2(0, Acc) ->
    array:from_list(Acc);
to_base2(N, Acc) ->
    to_base2(N div 2, [N rem 2|Acc]).
    
%Reverses the digits in the given number and returns the resulting number
reverse(N, Pow10) ->
    reverse(N, Pow10, 0).

reverse(0, _, Acc) ->
    Acc;
reverse(N, Pow10, Acc) ->
    reverse(N div 10, Pow10 div 10, Acc + (N rem 10)*Pow10).

%returns the maximum of two numbers
max(A, B) when A >= B -> A;
max(_A, B) -> B.
     
%return the minimum of two numbers
min(A, B) when A =< B -> A;
min(_A, B) -> B.

pow10(X) ->
    pow10(X, 0).

pow10(X, Acc) when X < 10 ->
    Acc;
pow10(X, Acc) ->
    pow10(X div 10, Acc + 1).
